package com.example.targetOffer.domain;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.LinkedList;

public class CQueue {
    private final static Logger log = LoggerFactory.getLogger(CQueue.class);
    //两个栈，一个出栈，一个入栈
    /** 要注意的是Stack类底层是一个Object[]数组，
     * 1。数组的新增-扩容（需要把旧数组中的所有元素向新数组中搬移 ）、
     * 2。数组的删除-移位（数组是连续的空间）
     * 都比较耗时
     *
     * LinkedList是双向链表结构，（其push、pop方法可实现栈先进后出的效果）
     * 链表的新增-扩容，删除-移位都比较快（分散存储，指针连接下一个）
     * */

    private final LinkedList<Integer> stack1;
    private final LinkedList<Integer> stack2;

    /**
     * @describe: 初始化两个栈
     * 栈1实现Queue的 appendTail() 方法： 用push的特性[先进后出]实现队列队尾添加元素的效果
     * 栈2实现Queue的 deleteHead() 方法： 用栈1的pop、栈2的push实现栈1元素的反转到栈2，以此实现队列删除队头元素的效果
     */
    public CQueue() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
        log.info("null");
    }

    /**
     * @fuction: 队列的队尾添加元素 // @describe: 利用栈的
     */
    public String appendTail(int value) {
        stack1.push(value);
        return null;
    }

    public int deleteHead() {
        if (!stack2.isEmpty()) {
            return stack2.pop();
        } else {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.isEmpty() ? -1 : stack2.pop();
        }
    }
}
